'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-06 16:51:42
'''
#
# @lc app=leetcode.cn id=1547 lang=python3
#
# [1547] 切棍子的最小成本
#

# @lc code=start
# 区间dp，考虑第一刀就行，可以推出递推关系。
from typing import List
class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        from sys import maxsize
        cuts = [0]+cuts +[n]
        cuts.sort()
        # dp中0和-1是边界设置。
        dp = [[0]*(len(cuts)) for _ in cuts]

        for dis in range(len(dp)-1):
            for i in range(1, len(dp)-1-dis):
                tmp = maxsize if dis else 0
                # 这里要记得边界处理，dis这个长度可以取到
                for k in range(dis+1):
                    tmp = min(tmp, dp[i][i+k-1]+dp[i+k+1][i+dis])
                dp[i][i+dis] = tmp+cuts[i+dis+1]-cuts[i-1]
        # print(dp)
        return dp[1][-2]
                
# @lc code=end

if __name__ == "__main__":
    solution = Solution()
    n = 7
    cuts = [1,3,4,5]
    print(solution.minCost(n, cuts))